this is the question:
One way to evaluate a prefix expression is to use a queue. To evaluate the expression, scan it repeatedly until the final expression value is known. In
each scan, read the tokens and store them in a queue. In each scan, replace an operator followed by two operands by the calculated values.
For example, the following expression is a prefix expression, which is evaluated to 159.
-+*9+28*+4863
We scan the expression and score it in a queue. During the scan, when an operator is followed by two operands, such as + 2 8, we put the result, 10 in the queue.
After the first scan, we have - + * 9 10 * 12 6 3
After the second scan, we have - + 90 72 3
After the third scan, we have - 162 3
After the fourth scan, we have 159
HERE IS THE APPROACH I TRIED:
1 .first take the char in expr[]="-+*9+28*+4863 ", calculate and put it in a queue .
2. again put t items in the queue to the expr[]= "-+*910*1263".
3. and repeat 1 and 2 till q->count is 1.
HERE IS THE CODE SO FAR I TRIED:
Code:
#include <stdio.h>
#include <stdlib.h>
#include<ctype.h>
#include<math.h>
typedef struct node
{
char data[8];
struct node *link;
} NODE;
typedef struct queue
{
NODE *front;
NODE *rear;
int count;
} QUEUE;
QUEUE* CreateQueue()
{
QUEUE* q = (QUEUE*)malloc(sizeof(QUEUE));
q->front = NULL;
q->rear = NULL;
q->count = 0;
return q;
}
void Enqueue(QUEUE *q, char *dataIn)
{
NODE *newNode = (NODE*)malloc(sizeof(NODE));
strcpy(newNode->data,dataIn);
newNode->link = NULL;
if (q->front == NULL)
q->front = newNode;
else
q->rear->link = newNode;
q->rear = newNode;
q->count++;
}
char* Dequeue(QUEUE *q)
{
char *dataout;
NODE *temp = q->front;
dataout = q->front->data;
if (q->count == 1)
q->rear = NULL;
q->front = q->front->link;
q->count--;
free(temp);
return dataout;
}
int QueueFront(QUEUE *q, char *dataOut)
{
if (q->count == 0)
return 0;
dataOut = q->front->data;
return 1;
}
int EmptyQueue(QUEUE *q)
{
if (q->count == 0)
return 1;
else
return 0;
}
int FullQueue(QUEUE *q)
{
NODE *temp = (NODE*)malloc(sizeof(NODE));
if (temp == NULL)
return 1;
else
{
free(temp);
return 0;
}
}
int QueueCount(QUEUE *q)
{
return q->count;
}
void DestroyQueue(QUEUE *q)
{
NODE *temp;
while (q->front != NULL)
{
temp = q->front;
q->front = q->front->link;
free(temp);
}
free(q);
}
int calculate(char a, int b, int c)
{
if(a=='+')
return (b+c);
else if(a=='-')
return (b-c);
else if(a=='*')
return (b*c);
else if(a=='/')
return (b/c);
}
int main()
{
char expr[]="-+9+28*+4863";
printf("%s",expr);
QUEUE *q = CreateQueue();
char data1[8],data2[8],data[8],data3[8],data4[8];
int i=0,j=1,k=2,l=0;
int a,b,r;
char *p,*datain,*dataOut;
p=data3;dataOut=data4;
while((QueueCount(q)>1))
{
i=0;j=1;k=3;l=0;
while((expr[i]!='\0'))
{
if(ispunct(expr[i])&&isdigit(expr[j])&&isdigit(expr[k]))
{
data1[0]=expr[j];data1[1]='\0';
data2[0]=expr[k];data2[1]='\0';
a=atoi(data1);b=atoi(data2);
r=calculate(expr[i],a,b);
//itoa (r, data, 10);
sprintf(data,"%d",r);
datain=data;
Enqueue(q, datain);
i=i+3;j=j+3;k=k+3;
}
else
{
data[0]=expr[i];data[1]='\0';
datain=data;
Enqueue(q,datain);
i++;j++;k++;
}
}
while(EmptyQueue(q))
{
dataOut=Dequeue(q);
expr[l]=*dataOut;
l++;
}
expr[l]='\0';
}
return 0;
}
i am facing problem in the last while loop.
here i don't know how to convert string to char again and put in the expr[].
now i feel that my approach is wrong, could somebody help me ..